package graph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

public class Graph {

    private final int MAX_SIZE = 10;
    
    private List<Vertex> vertexList;
    private byte[][] adjMat;
    private int nVerts;
    
    public Graph() {
        vertexList = new ArrayList<Vertex>();
        adjMat = new byte[MAX_SIZE][MAX_SIZE];
        for (int row = 0; row < MAX_SIZE; row++) {
            for (int colm = 0; colm < MAX_SIZE; colm++) {
                adjMat[row][colm] = 0;
            }
        }
    }
    
    public void addVertex(Vertex vertext) {
        if (nVerts > MAX_SIZE) {
            return;
        }
        vertexList.add(vertext);
        nVerts++;
    }
    
    public void addVertex(char label) {
        vertexList.add(new Vertex(label));
        nVerts++;
    }
    
    public void addEdge(int start, int end) {
        adjMat[start][end] = 1;
        adjMat[end][start] = 1;
    }
    
    public void addDirectedEdge(int start, int end) {
        adjMat[start][end] = 1;
    }
    
    public void displayVertex(Vertex vertex) {
        System.out.print(vertex.getLabel());
    }
    
    /*
     * Graph depth-first search
     */
    public void dfs() {
        Stack<Integer> stack = new Stack<Integer>();
        vertexList.get(0).setWasVisited(true);
        this.displayVertex(vertexList.get(0));
        stack.push(new Integer(0));
        
        while(!stack.isEmpty()){
            int location = this.getUnvisitedVertext(stack.peek());
            
            if (location == -1) {
                stack.pop();
            } else {
                vertexList.get(location).setWasVisited(true);
                this.displayVertex(vertexList.get(location));
                stack.push(new Integer(location));
            }
        }
        /*
         * reset all the status
         */
        for(Vertex vertex: vertexList) {
            vertex.setWasVisited(false);
        }
    }
    
    /*
     * Graph breadth-first search
     */
    public void bfs() {
        Queue<Integer> queue = new LinkedList<Integer>();
        vertexList.get(0).setWasVisited(true);
        this.displayVertex(vertexList.get(0));
        queue.add(new Integer(0));
        while(!queue.isEmpty()) {
            int location = getUnvisitedVertext(queue.peek());
            if (location == -1) {
                queue.poll();
            } else {
                queue.add(new Integer(location));
                this.displayVertex(vertexList.get(location));
                vertexList.get(location).setWasVisited(true);
            }
        }
        
        //reset all the status 
        for (Vertex vertex: vertexList) {
            vertex.setWasVisited(false);
        }
    }
    
    /*
     * find the minimum spanning tree
     */
    public void mst() {
        Stack<Integer> stack = new Stack<Integer>();
        vertexList.get(0).setWasVisited(true);
        stack.push(new Integer(0));
        while (!stack.isEmpty()) {
            int currentLoc = stack.peek();
            int location = this.getUnvisitedVertext(currentLoc);
            if (location == -1) {
                stack.pop();
            } else {
                stack.push(new Integer(location));
                vertexList.get(location).setWasVisited(true);
                this.displayVertex(vertexList.get(currentLoc));
                this.displayVertex(vertexList.get(location));
                System.out.print(" ");
            }
        }
    }
    
    public void topo() {
        Stack<Integer> stack = new Stack<Integer>();
        int location = noSuccessor();
        while (location != -1) {
            stack.push(location);
            vertexList.get(location).setWasVisited(true);
            removeEdge(location);
            location = noSuccessor();
        }
        
        while (!stack.isEmpty()) {
            this.displayVertex(vertexList.get(stack.pop()));
        }
    }
    
    public void removeEdge(int v) {
        for (int i = 0; i < nVerts; i++) {
            adjMat[i][v] = 0;
        }
    }
    
    public int noSuccessor() {
        for (int i = 0; i < nVerts; i++) {
            boolean hasEdge = false;
            for (int j = 0; j < nVerts; j++) {
                if (adjMat[i][j] == 1) {
                    hasEdge = true;
                    break;
                }
            }
            if (hasEdge == false && vertexList.get(i).getWasVisited() == false) {
                return i;
            }
        }
        return -1;
    }
    
    /*
     * returns an unvisited vertex adj to v
     */
    public int getUnvisitedVertext(int v) {
        for (int i = 0; i < nVerts; i++) {
            if (adjMat[v][i] == 1 && vertexList.get(i).getWasVisited() == false) {
                return i;
            }
        }
        return -1;
    }
}
